(1) Field of the Invention
The invention relates to a multi-objective optimization method that evaluates a plurality of objective functions to determine the best decision variables satisfying those objectives.
(2) Description of the Prior Art
An agent designed to operate in the real physical world, must deal with the aspect of unpredictability in the environment. An unpredictable event may be something that is out of an agent's control (a car turning into it's path) or an event that is simply left out of the agent's reasoning scope (an on-schedule train crossing its path). The ability to react to unforeseen events makes life simpler for the agent by requiring it to predict less about the world and allowing it to avoid forming contingency plans for perhaps countless possible deviations from a long term plan. The interest in behavior-based robotics is tied directly to the interest in building robots or agents that are to be situated in such dynamic environments. Brooks (1991a) stated that traditional artificial intelligence was dominated by a preoccupation with search techniques which in turn promoted an “abandonment of any notion of situatedness” since simulated environments were sufficient for test and evaluation. The behavior-based control architecture has been found by many to be a viable architecture in situations where the environment is too complex for a single comprehensive world model, and the ability to react quickly to changes in the environment is especially important. (Brooks, 1986; Rosenblatt, 1997; Arkin, 1998; Pirjanian, 1998; Riekki, 1999). Each behavior specializes in one particular aspect of the overall task of the vehicle, thereby simplifying the implementation of each behavior. Unfortunately, the behaviors often disagree on what next action is best for the vehicle and a workable arbitration scheme therefore becomes necessary. Simple arbitration schemes often either suppress all but the most important behavior, or merely average or convolve a single action from multiple behaviors, which lead to unacceptable shortcomings in overall vehicle behavior. Effective coordination of behaviors requires each behavior to not only produce the one action that best serves the goals of the behavior, but also produce alternative actions that may lead to the best overall compromise between behaviors. By rating all possible actions, the behavior is in effect producing an objective function over the domain of all possible vehicle actions, and action selection then can be viewed as a multi-objective optimization problem. Unfortunately, the action domain grows exponentially with respect to the number of action variables, and requiring each behavior to explicitly rate all actions becomes computationally infeasible in all but the simplest applications.
One architecture for solving these problems is the subsumption architecture, introduced in Brooks (1986). To overcome slow reaction times, at each layer (or behavior), there is a tight coupling between sensors and actuators, and a commitment is made only to the next action. A lower, fundamental behavior such as avoiding obstacles, could take quick control, suppressing or ignoring higher level behaviors. To overcome the pitfalls of relying on a complete world model, each behavior is responsible for taking whatever it needs from the environment for its own limited world perspective. No communication or model sharing is proposed between behaviors. The decentralized nature of the model also contributes to a modular design process and robust performance, and has the effect that overall intelligence attributed to the agent tends to be seen as an emergent property of performance, rather than due to a single grand design. A layered design implies a prioritization of behaviors and thus a policy for choosing an action when different behaviors are in conflict. Control of the vehicle alternates between behaviors while the action preferences of other behaviors are ignored completely. This can be viewed as a serious shortcoming if the desire is for the agent to react simultaneously to more than one event, or react in a way that is consistent with longer term plans.
Other models such as those taught by Arkin (1989b); Payton et al. (1990); Maes (1990), have tried to address these issues, and cooperative action selection, where an action can be influenced by two or more behaviors simultaneously, has since been common. Behavior-based implementations are typically thought of as containing a separate, distinct component responsible for action selection. As an example, the distributed architecture for mobile navigation (DAMN) proposed in Rosenblatt (1997) contains an arbiter that receives votes from each behavior. Although action selection typically is the only source of communication (albeit one-way) between behaviors, there must be some degree of uniformity in how they communicate to the action selection process, since behaviors are likely to be heterogeneous in their implementation. In the DAMN architecture, this communication comes in the form of the weighted votes over a common set of action choices known to all behaviors. In general, there is a tradeoff to be made between the complexity of the information being passed from the behaviors and the complexity burden put on the action selection method. On one hand, by emphasizing quick decisions, there is the risk of sacrificing the quality of the decision. On the other hand, by emphasizing quality decisions, there is the risk of sacrificing the quickness of the decision.
A strength of the behavior-based architecture is its modularity and ability to accept additional behaviors into an existing system without redesigning existing behaviors. Opinions have varied, however, as to what constitutes a behavior. In Brooks (1986), behaviors were devoid of any internal model or representation of the world, and behaviors were thought of as direct mappings from sensory input to actions. Brooks (1989, pp. 449–450) advocated using the world itself as the only model utilized by behaviors.
Choosing a particular action involves attempting to choose a correct action in the shortest amount of time. Various action selection methods are provided in the prior art. These methods include no-compromise methods wherein one behavior is chosen and other behaviors are ignored. The problem becomes choosing the appropriate behavior. The defect of this approach is that when one behavior is chosen, a decision that is satisfactory to many of the other behavior can be ignored because they weren't the first choice for top behavior. Compromise methods are subdivided into single fusion compromise methods and multifusion compromise methods. In single fusion compromise methods, the choices of all of the behaviors are combined as by averaging. The problem with single fusion compromise methods is that they can lead to a compromise that is unsatisfying to both behaviors. Multifusion compromise methods are divided into single dimension and high dimension methods. In multifusion compromise methods compromising is performed by considering mutually agreeable alternatives and choosing one that comes with the highest combined backing from the contributing behaviors. When this involves only one action variable, this represents a single dimension multifusion compromise method. Additional action variables give rise to high dimension multifusion compromise methods. A primary problem of these methods is the computational burden required to determine the action variable in a timely manner.
The competing actions can be determined by implicit evaluation and explicit evaluation. Voting is one explicit evaluation method in which each behavior function votes for an action. In voting, each possible action is explicitly evaluated to provide a candidate, and the candidate receiving the most votes is chosen. Voting can be applied to all forms of behavior functions but it is computationally intensive. Implicit evaluation can be performed by using analytical methods to find local maxima. These local maxima can be used to represent a large number of possible actions thereby speeding the decision process. However, local maxima are not easily determined for all forms of behavior functions.